package org.example.myleet.p738;

/**
 * 思路：
 *  从右向左扫描数字，若发现当前数字比其左边一位（较高位）小，
 *  则把其左边一位数字减1，并将该位及其右边的所有位改成9
 */
public class Solution {
    public int monotoneIncreasingDigits(int N) {
        //先将整数化为数字数组便于遍历
        String numStr = String.valueOf(N);
        char[] digitChars = numStr.toCharArray();
        int[] digits = new int[digitChars.length];
        for (int i=0; i<digitChars.length; i++) {
            digits[i] = (int)digitChars[i] - (int)'0';
        }
        int idx = digits.length-1;
        //从右边一直检查到左边，直到数字升序为止
        while (!monotoneIncrease(digits)) {
            if (idx > 0) {
                digits[idx] = 9;
                --digits[idx-1];
                if (digits[idx-1] < 0) {
                    while (idx > 0 && digits[idx-1] < 0) {
                        --idx;
                        digits[idx] = 9;
                        --digits[idx-1];
                    }
                }
            }
        }
        int answer = 0;
        for (int i=0; i<digits.length; i++) {
            answer = answer * 10 + digits[i];
        }
        return answer;
    }

    private boolean monotoneIncrease(int[] digits) {
        for (int i=1; i<digits.length; i++) {
            if (digits[i] < digits[i-1]) {
                return false;
            }
        }
        return true;
    }
}
